class Solution
{
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        int longestPalindromeSize = 1;
        int longestPalindromeBegin = 0;
        for (int i = 0; i < n; ++i)
        {
            int j = 1;
            while (i - j >= 0 && i + j < n && s[i - j] == s[i + j])
            {
                ++j;
            }
            int k = 0;
            while (i - k >= 0 && i + 1 + k < n && s[i - k] == s[i + 1 + k])
            {
                ++k;
            }
            int oddPalindromeLen = 1 + 2 * (j - 1);
            int evenPalindromeLen = 2 * k;
            if (oddPalindromeLen > longestPalindromeSize)
            {
                longestPalindromeSize = oddPalindromeLen;
                longestPalindromeBegin = i - j + 1;
            }
            if (evenPalindromeLen > longestPalindromeSize)
            {
                longestPalindromeSize = evenPalindromeLen;
                longestPalindromeBegin = i - k + 1;
            }
        }
        return s.substr(longestPalindromeBegin, longestPalindromeSize);
    }
};